#include <stdio.h>
#define HASHSIZE 362880
#define MAXINT 9

typedef struct node
{
    int list;
    int hash;
    int deep;
    int Hvalue1;
    int Hvalue2;
    int record;
    struct node * next;
    struct node * pre;
}node;

node Path [HASHSIZE];

int ListValue (int List[MAXINT])
{
    int sum = 0;
    for(int i = 0;i < MAXINT;i++)
    {
        sum *= 10;
        sum += List[i];
    }
    return sum;
}

int InitMul[MAXINT] = {40320, 5040, 720, 120, 24, 6, 2, 1, 1};

int H1Score[HASHSIZE], H2Score[HASHSIZE];

int HashValue (int list[MAXINT])
{
    int templist[MAXINT];
    int sum = 0;
    for(int i = 0;i < MAXINT;i++)
    {
        templist[i] = 0;
        for(int j = 0;j < i;j++)
            if(list[j] < list[i])
                templist[i]++;
    }

    for(int i = 0;i < MAXINT;i++)
        sum += (list[i] - templist[i]) * InitMul[i];

    return sum;  
}

int H2 (int list[MAXINT])
{
    int dis (int listi, int pos);

    int sum = 0;
    for(int i = 0;i < MAXINT;i++)
        sum += dis(list[i],i);
    return sum;
}

int dis (int listi, int pos)
{
    if(!listi)
        return 0;
    int k_x = (listi-1)%3;
    int k_y = (listi-1)/3;
    int d_x = pos % 3;
    int d_y = pos / 3;
    int d1 = (k_x > d_x)? (k_x - d_x): (d_x - k_x);
    int d2 = (k_y > d_y)? (k_y - d_y): (d_y - k_y);
    return d1+d2;
}

int Heuristic (int list[MAXINT])
{
    int sum = 0;
    for(int i = 0;i < MAXINT;i++)
        if(list[i] != i+1)
            sum++;
    return sum;
}

void perm (int * list, int k)
{
    void swap (int * a, int * b);
    int HashValue (int list[MAXINT]);
    void push (int k);
    int CheckInStack (int k);
    int Heuristic (int list[MAXINT]);

    if(k >= MAXINT)
        return ;
    else if(k == MAXINT - 1)
    {
        int hash = HashValue(list);
        Path[hash].hash = hash;
        Path[hash].list = ListValue(list);
        H1Score[hash] = Heuristic(list);
        H2Score[hash] = H2(list);
        Path[hash].Hvalue1 = H1Score[hash];
        Path[hash].Hvalue2 = H2Score[hash];   
    }
    for(int i = k;i < MAXINT;i++)
    {
        swap(&list[i],&list[k]);
        perm(list,k+1);
        swap(&list[i],&list[k]);
    }
}

void swap (int * a, int * b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void PreHandlePath (void)
//预处理Path数组
{
    void InitHash(void);
    int list[MAXINT] = {0,1,2,3,4,5,6,7,8};
    void perm (int * list, int k);

    InitHash();

    for(int i = 0;i < HASHSIZE;i++)
        H1Score[i] = H2Score[i] = -1;
    perm(list,0);

    for(int i = 0;i < HASHSIZE;i++)
        if(H1Score[i] == -1 || H2Score[i] == -1)
            printf("Error! %d is -1!\n",i);
}

void InitHash (void)
{
    for(int i = 0;i < HASHSIZE;i++)
    {
        Path[i].deep = -1;
        Path[i].record = 0;
        Path[i].pre = Path[i].next = NULL;
    }
}
